package com.LeeCode;

import java.util.Arrays;

/**
 * 每一个查询的最大美丽值
 */

public class Code2070 {
    public static void main(String[] args) {
        int[][] items = {
                {1, 2},
                {3, 2},
                {2, 4},
                {5, 6},
                {3, 5}
        };

        int[] queries = {1, 2, 3, 4, 5, 6};
        System.out.println(Arrays.toString(new Code2070().maximumBeauty(items, queries)));
    }

    public int[] maximumBeauty(int[][] items, int[] queries) {
        Arrays.sort(items, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            } else {
                return a[0] - b[0];
            }
        });
        int max = items[0][1];
        for (int i = 1; i < items.length; i++) {
            max = Math.max(max, items[i][1]);
            items[i][1] = max;
        }

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int pos = lowerBound(items, queries[i] + 1) - 1;
            ans[i] = pos == -1 ? 0 : items[pos][1];
        }
        return ans;
    }

    private int lowerBound(int[][] items, int target) {
        int left = -1, right = items.length, mid;
        while (left + 1 < right) {
            mid = left + (right - left) / 2;
            if (items[mid][0] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}
